#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

// 128.最长连续序列
// 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
//
//请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> set;
        for(int e : nums)
            set.insert(e);

        int count = 0;
        int res = 0;
        for(int n: set) {
            if(set.find(n-1) == set.end()) {
                // 说明这部分是开始的数据：头
                count = 1;
                int curr = n;
                while(set.find(curr+1) != set.end()) {
                    // 如果存在，说明是：中
                    count++;
                    curr++;
                }
                // 结束了说明到了：尾
                res = max(res,count);
            }
        }
        return res;
    }
};
int main() {
    int nums1[6] = {100, 4, 200, 1, 3, 2};
    vector<int> vec1(nums1, nums1 + sizeof(nums1)/sizeof(int));
    cout << Solution().longestConsecutive(vec1) << endl;
    // 4

    // ---

    int nums2[4] = {1, 2, 0, 1};
    vector<int> vec2(nums2, nums2 + sizeof(nums2)/sizeof(int));
    cout << Solution().longestConsecutive(vec2) << endl;
    // 3
    return 0;
}
